#include "LinkList.h"
#include <iostream>

LinkList::LinkList():size(0)
{
    /*因为数组里有Node *head;指针，所以初始化他*/
    head = new Node(0); //头结点
}

LinkList::LinkList(const LinkList& list)
{
    size = 0;
    head = new Node(0);
    Node *travelPoint = list.head->next;
    while(travelPoint != nullptr)
    {
        InsertTail(travelPoint->value);
        travelPoint = travelPoint->next;
    }
}

LinkList::~LinkList()
{
    while(head != nullptr)
    {
        //记录下一个节点指针
        Node *nextNode = head->next;
        //放掉当前指针
        delete head;
        //head指针往后走
        head = nextNode;
    }
}

//尾插  O(n)-> head头指针不能动,设置一个  遍历指针  遍历链表
void LinkList::InsertTail(const ElementType& element)
{
    /*遍历指针*/
    Node *travelPoint = head;
    /*找尾部*/
    while(travelPoint->next != nullptr)  //next是当前节点的指针域，里面存放下一个节点的地址
    {
        travelPoint = travelPoint->next;
    }
    /*出循环时，travelPoint->next一定为空，此时在尾部插入新的节点*/
    //在尾部插入新的节点
    travelPoint->next = new Node(element);
    size++;
}

//头插 O(1)
void LinkList::InsertHead(const ElementType& element)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

//中间插  O(n)
void LinkList::InsertByIndex(int index, const ElementType& element)
{
    if(index < 0 || index > size)
    {
        return;
    }
    /*谨慎*/
    Node *travelPoint = head;
    /*谨慎*/
    for(int i = 0; i < index; i++) //实际index-1的位置
    {
        travelPoint = travelPoint->next;
    }
    //创建新节点
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    travelPoint->next = newNode;
    size++;
}

//按位置删除    O(n)
void LinkList::RemoveByIndex(int index)
{
    if(index < 0 || index >= size)
    {
        return;
    }
    /*谨慎*/
    Node *travelPoint = head;
    /*谨慎*/
    for(int i = 0; i < index; i++)  //实际index-1的位置
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    delete freeNode;
    size--;
}

//按值删除
void LinkList::RemoveByElement(const ElementType& element)
{
    Node *travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->value == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
        {   
            //相邻的两个相同的数
            travelPoint = travelPoint->next;
        }       
    } 
}

//按位置修改
void LinkList::UpDataByIndex(int index, const ElementType& element)
{
    if(index < 0 || index >= size)
    {
        return;
    }
    Node *travelPoint = head;
    for(int i = 0; i <= index; i++)  
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->value = element;
}

//按值修改
void LinkList::UpDataByElement(const ElementType& oldValue, const ElementType& newValue)
{
    /*找和值有关的head->next; 和位置有关的head;*/
    Node *travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value == oldValue)
        {
            travelPoint->value = newValue;
        }
        travelPoint = travelPoint->next;
    }
}

//链表排序
/*冒泡排序*/
void LinkList::BubbleSort()
{
    for(int i = 0; i < size - 1; i++)
    {
        Node *travelPoint = head; //从头开始扫描链表
        for(int j = 0; j < size - i - 1; j++)
        {
            if(travelPoint->next->value > travelPoint->next->next->value)
            {
                Node *prevNode = travelPoint->next;
                Node *nextNode = prevNode->next;
                travelPoint->next = nextNode;
                prevNode->next = nextNode->next;
                nextNode->next = prevNode;
            }
            travelPoint = travelPoint->next;
        }
    }
}

//归并
LinkList LinkList::Merge(const LinkList& list)
{
    LinkList result;
    Node *p1 = head->next;
    Node *p2 = list.head->next;
    //当两个指针都没有走到头时
    while(p1 && p2)
    {
        if(p1->value < p2->value)
        {
            result.InsertTail(p1->value);
            p1 = p1->next;
        }
        else if(p1->value == p2->value)
        {
            result.InsertTail(p2->value);
            result.InsertTail(p1->value);
            p1 = p1->next;
            p2 = p2->next;
        }
        else
        {
            result.InsertTail(p2->value);
            p2 = p2->next;
        }
    }
    //循环结束，剩余的一方插入
    while(p1)
    {
        result.InsertTail(p1->value);
        p1 = p1->next;
    }
    while(p2)
    {
        result.InsertTail(p2->value);
        p2 = p2->next;
    }
    return result;
}

void LinkList::show()
{
    std::cout<<"size: "<<size<<std::endl;
    //存有效数据的第一个节点
    //找和值有关的head->next;
    Node *travelPoint = head->next;
    //当前指针不为空，节点存在
    while(travelPoint != nullptr)
    {
        std::cout<<travelPoint->value<<" "; //打印数据域
        travelPoint = travelPoint->next; //访问下一个节点
    }
    std::cout<<std::endl;
}

void LinkList::Sort()
{
    FastSort(head->next, nullptr);
}

/*快速排序*/
void LinkList::FastSort(Node *start, Node *end)
{
    //递归终止条件
    if(start == end)
        return;
    Node *temp = start;  //基准值指针
    Node *slow = start;  //慢指针
    Node *fast = start->next; //快指针
    while(fast != end)
    {
        //快指针所指的数据比基准值小
        if(fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(fast->value, slow->value);
        }
        fast= fast->next;
    }
    std::swap(temp->value, slow->value);
    FastSort(start, slow);
    FastSort(slow->next, end);   
}

/***链表逆序***/ 
void LinkList::Reserve()
{
    // 前一个节点的指针，初始为nullptr，因为逆序后头节点会指向nullptr
    Node *prev = nullptr;
    // 当前节点的指针，初始为链表的第一个节点
    Node *cur = head->next;
    // 下一个节点的指针，初始为当前节点的下一个节点
    Node *Next = cur->next;
    while(Next != nullptr)
    {
        // 当前节点指向前一个节点，实现逆序
        cur->next = prev;
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    cur->next = prev; //最后一个节点单独逆序
    head->next = cur;
}

/****逆序递归****/
void LinkList::Reserve2()
{
    head->next = Reserve2(head->next);
}

/****逆序递归****/
LinkList::Node *LinkList::Reserve2(Node *node)
{
    //返回值是新链表的头
    //终止条件
    if(node->next == nullptr) //原来的尾巴是新的头
        return node;
    else
    {
        Node *newHeader = Reserve2(node->next);
        node->next->next = node; //逆序, 将当前节点的下一个节点的next指针指向当前节点，实现链表逆序
        node->next = nullptr; //新的尾巴next指针指向空, 成为新的尾节点
        return newHeader; //返回逆序后的新链表的头节点
    }
}

